CC system

In computational geometry, a CC system or counterclockwise system is a ternary relation pqr that satisfies the axioms:

  1. Cyclic symmetry: If pqr then qrp.
  2. Antisymmetry: If pqr then not prq.
  3. Nondegeneracy: Either pqr or prq.
  4. Interiority: If tqr and ptr and pqt, then pqr.
  5. Transitivity: If tsp and tsq and tsr, and tpq and tqr, then tpr.

CC systems were defined by Donald Knuth, who wanted to understand problems in planar geometry. Knuth proved that CC systems were essentially equivalent to a class of oriented matroids.[1] The enumerative combinatorics of CC systems had been pursued by computational geometers studying "horizon theorems" before Knuth.[2]

Notes

  1. ^ There exists a two-to-one correspondence between CC systems and "uniform acyclic oriented matroids of rank 3", according to Knuth (1992, p. 40).
  2. ^ Horizon theorems had been discovered independently by Chazelle, Guibas & Lee (1985, Lemma 1) and Edelsbrunner, O'Rouke & Seidel (1986, Theorem 2.7) and then refined by Bern et al. (1991, p. 40), according to Knuth (1992, p. 96–97), who also mentions the textbook presentation in Edelsbrunner (1987, Chapter 5 "Zones in arrangements" (pp. 83–96)).

References